#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<bool>>visted(m, vector<bool>(n, false));
        int result = 0;
        dfs(visted, m, n, cnt, 0, 0, result);
        return result;
    }
private:
    void dfs(vector<vector<bool>>& visted, int m, int n, int cnt, int i, int j, int& result) {
        if (i >= m || j >= n || visted[i][j] || isvaild(i, j, cnt)) { return; }
        visted[i][j] = true;
        result++;
        dfs(visted, m, n, cnt, i, j + 1, result);
        dfs(visted, m, n, cnt, i + 1, j, result);
    }
    bool isvaild(int i, int j, int cnt) {
        int a = 0;
        int b = 0;
        while (i) {
            a += i % 10;
            i = i / 10;
        }
        while (j) {
            b += j % 10;
            j = j / 10;
        }
        return a + b > cnt;
    }
};